#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
using namespace std;

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        //背包问题
        //dp[i][j]只考虑前i个数，目标等于j的个数
        vector<int> dp(target+1);
        
        //初始化
        //考虑前一个数


        
            for(int j=1;j<target+1;++j){
                // dp[i][j] = dp[i-1][j];
                for(int index = nums.size()-1;index>=0;--index){
                    if(j-nums[index]>0&&dp[j-nums[index]]<INT_MAX-dp[j]){
                        dp[j] += dp[j-nums[index]];
                    }
                    else if(j-nums[index]==0){
                        dp[j] +=1;
                    }
                }
            }
        
        return dp[target];    
    }
};

int main(){
    Solution S;
    vector<int> nums = {10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,250,260,270,280,290,300,310,320,330,340,350,360,370,380,390,400,410,420,430,440,450,460,470,480,490,500,510,520,530,540,550,560,570,580,590,600,610,620,630,640,650,660,670,680,690,700,710,720,730,740,750,760,770,780,790,800,810,820,830,840,850,860,870,880,890,900,910,920,930,940,950,960,970,980,990,111};
    cout<<S.combinationSum4(nums,999)<<endl;
    return 0;
}